import java.util.ArrayList;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class InsertInterval {

	class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	public ArrayList<Interval> insert(ArrayList<Interval> intervals,
			Interval newInterval) {
		ArrayList<Interval> res = new ArrayList<Interval>();
		int n = intervals.size();
		int i = 0;
		while (i < n && intervals.get(i).end < newInterval.start) {
			res.add(intervals.get(i));
			i++;
		}
		if (i < n) {
			newInterval.start = Math.min(newInterval.start,
					intervals.get(i).start);
		}
		while (i < n && intervals.get(i).start <= newInterval.end) {
			i++;
		}
		if (i > 0) {
			newInterval.end = Math.max(newInterval.end,
					intervals.get(i - 1).end);
		}
		res.add(newInterval);
		while (i < n) {
			res.add(intervals.get(i));
			i++;
		}
		return res;
	}

	public static void main(String[] args) {

	}

}
